package primary.code09_dynamicTree;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 多叉树的结构，直属领导持有直接下属的集合
 * 若直属领导参加派对，则直接下属不参加
 * 每个员工都有自己的快乐值
 * 求本次派对的最大快乐值
 * <p>
 * 1. 不包含本节点，包含本节点
 * 2. 最大快乐值
 * 3. 不包含本节点：下一级子节点最大快乐值求和；包含本节点：本节点快乐值 + 下下一级子节点最大快乐值求和
 */
@Slf4j
public class Code02_MaxHappiness {

    static class Node {
        int val;
        List<Node> sub = new ArrayList<>();

        public Node(int val) {
            this.val = val;
        }
    }

    public static int maxHappiness(Node root) {
        if (root == null) return 0;

        List<Node> children1 = root.sub;
        int notInvitedMaxHappiness = 0;
        for (Node child1 : children1) {
            notInvitedMaxHappiness += maxHappiness(child1);
        }

        int invitedMaxHappiness = root.val;
        for (Node child1 : children1) {
            for (Node child2 : child1.sub) {
                invitedMaxHappiness+=maxHappiness(child2);
            }
        }
        return Math.max(notInvitedMaxHappiness, invitedMaxHappiness);
    }

    public static void main(String[] args) {
        Node root = new Node(4);

        Node n11 = new Node(3);
        Node n12 = new Node(8);

        Node n21 = new Node(2);
        Node n22 = new Node(4);

        Node n23 = new Node(7);
        Node n24 = new Node(9);

        Node n31 = new Node(10);

        root.sub.add(n11);
        root.sub.add(n12);

        n11.sub.add(n21);
        n11.sub.add(n22);

        n12.sub.add(n23);
        n12.sub.add(n24);

        n24.sub.add(n31);
        //ans: 27
        log.info("max happiness is {}", maxHappiness(root));
    }

}
